Floyd-Warshall Algorithm

플로이드-워샬 알고리즘(Floyd-Warshall Algorithm)
동적 프로그래밍
\Theta(V^3) 시간에 수행된다.
d(k)ij={wijmin(d(k−1)ij,d(k−1)ik+d(k−1)kj)
#include <iostream>
#include <climits>
#include <algorithm>
template <typename T>
struct Matrix{
int eN, vN;
T** data;
Matrix(int _vN): vN(_vN) {
data=new T*[this->vN];
for(int i=0; i<vN; ++i) data[i]=new T[this->vN];
}
Matrix(const Matrix& other){
this->vN=other.vN;
this->eN=other.eN;
this->data=new T*[this->vN];
for(int i=0; i<this->vN; ++i){
this->data[i]=new T[this->vN];
}
for(int i=0; i<this->vN; ++i){
for(int j=0; j<this->vN; ++j) this->data[i][j]=other.data[i][j];
}
}
~Matrix(){
for(int i=0; i<this->vN; ++i) delete[] this->data[i];
delete[] this->data;
}
Matrix& operator=(const Matrix& other){
this->vN=other.vN;
this->eN=other.eN;
for(int i=0; i<this->vN; ++i){
for(int j=0; j<this->vN; ++j){
this->data[i][j]=other[i][j];
}
}
return *this;
}
T* operator[](int ind) const {
return this->data[ind];
}
void makeD(T W[][3], int _eN){
this->eN=_eN;
for(int i=0; i<this->vN; ++i){
for(int j=0; j<this->vN; ++j){
if(i==j) this->data[i][j]=0;
else this->data[i][j]=INT_MAX;
}
}
for(int i=0; i<this->eN; ++i){
this->data[W[i][0]-1][W[i][1]-1]=W[i][2];
}
}
void print(void){
for(int i=0; i<this->vN; ++i){
for(int j=0; j<this->vN; ++j){
std::cout<<this->data[i][j]<<' ';
}
std::cout<<'\n';
}
std::cout<<std::endl;
}
};
template <typename T>
Matrix<T> FloydWarshall(const Matrix<T>& W){
int n=W.vN;
Matrix<T> D=W;
for(int k=0; k<n; ++k){
Matrix<T> tmpD(n);
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
if(D[i][k]==INT_MAX || D[k][j]==INT_MAX) tmpD[i][j]=D[i][j];
else tmpD[i][j]=std::min(D[i][j], D[i][k]+D[k][j]);
}
}
D=tmpD;
}
return D;
}
int main(void){
const int eN=9, vN=5;
int Edge[eN][3]={
{1, 2, 3}, {1, 3, 8}, {1, 5, -4},
{2, 4, 1}, {2, 5, 7}, {3, 2, 4},
{4, 1, 2}, {4, 3, -5}, {5, 4, 6}
};
Matrix<int> D0(vN);
D0.makeD(Edge, eN);
Matrix<int> Dn=FloydWarshall<int>(D0);
Dn.print();
return 0;
}
방향 그래프(이행적 폐쇄)
각 쌍에 대하여, 이동 가능 유무를 검사하기 위해 행렬 E or T 를 생성한다.

E:
각 가중치에 대해 1의 가중치를 부여한 후, 플로이드 워샬 알고리즘을 수행하면 얻을 수 있다.
(d_ij<n인 경우 경로가 존재한다.)
T t(0)ij={01 i≠j 그리고 (i,j)∉E 인 경우 tij=0 i=j 또는 (i,j)∈E 인 경우 tij=1 t(k)ij=t(k−1)ijOR (t(k−1)ikand t(k−1)kj)
#include <iostream>
#include <climits>
#include <algorithm>
template <typename T>
struct Matrix{
int eN, vN;
T** data;
Matrix(int _vN): vN(_vN) {
data=new T*[this->vN];
for(int i=0; i<vN; ++i) data[i]=new T[this->vN];
}
Matrix(const Matrix& other){
this->vN=other.vN;
this->eN=other.eN;
this->data=new T*[this->vN];
for(int i=0; i<this->vN; ++i){
this->data[i]=new T[this->vN];
}
for(int i=0; i<this->vN; ++i){
for(int j=0; j<this->vN; ++j) this->data[i][j]=other.data[i][j];
}
}
~Matrix(){
for(int i=0; i<this->vN; ++i) delete[] this->data[i];
delete[] this->data;
}
Matrix& operator=(const Matrix& other){
this->vN=other.vN;
this->eN=other.eN;
for(int i=0; i<this->vN; ++i){
for(int j=0; j<this->vN; ++j){
this->data[i][j]=other[i][j];
}
}
return *this;
}
T* operator[](int ind) const {
return this->data[ind];
}
void makeD(T W[][3], int _eN){
this->eN=_eN;
for(int i=0; i<this->vN; ++i){
for(int j=0; j<this->vN; ++j){
if(i==j) this->data[i][j]=0;
else this->data[i][j]=INT_MAX;
}
}
for(int i=0; i<this->eN; ++i){
this->data[W[i][0]-1][W[i][1]-1]=W[i][2];
}
}
void print(void){
for(int i=0; i<this->vN; ++i){
for(int j=0; j<this->vN; ++j){
std::cout<<this->data[i][j]<<' ';
}
std::cout<<'\n';
}
std::cout<<std::endl;
}
bool include(int i, int j){
if(this->data[i][j]!=INT_MAX && this->data[i][j]!=0) return true;
else return false;
}
};
template <typename T>
Matrix<bool> TransitiveClosure(Matrix<T> E){
int n=E.vN;
Matrix<bool> T0(n);
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
if(i==j || E.include(i, j))T0[i][j]=true;
else T0[i][j]=false;
}
}
for(int k=0; k<n; ++k){
Matrix<bool> T1(n);
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
T1[i][j]=T0[i][j]|(T0[i][k]&T0[k][j]);
}
}
T0=T1;
}
return T0;
}
int main(void){
const int eN=5, vN=4;
int Edge[eN][3]={
{4, 1, 1}, {2, 4, 1}, {2, 3, 1}, {3, 2, 1}, {4, 3, 1}
};
Matrix<int> G(vN);
G.makeD(Edge, eN);
Matrix<bool> Tn=TransitiveClosure<int>(G);
Tn.print();
return 0;
}